package com.jin.spirng_boot_learn.rbtree;

public class RBtree {


    private Node root;


    public Node getRoot() {
        return root;
    }


    public void add(Node node) {
        if (root == null) {
            node.setColor(Node.BLACK);
            this.root = node;
        } else {
            node.setColor(Node.RED); // 加入节点 默认是红色的
            doAdd(node);
        }

    }


    /**
     * 我们先当红黑树为普通的二叉搜索树一样插入节点，并将其颜色置为RED
     * 然后调整 树的平衡性
     * @param node
     */
    private void doAdd(Node node) {
        // 找到要插入的位置
        Node target = findTarget(root, node);
        if (target.getValue() >= node.getValue()) {
            target.setLeft(node);
        } else{
            target.setRight(node);
        }
        node.setFather(target);
        checkBalance(node);
    }

    /**
     * 双红相邻
     * 叔叔节点 红色  直接祖父节点和父亲变色
     *
     * 双红相邻
     * 叔叔节点 黑色  自己是左  右旋   旋转节点黑色  下面的红色
     *
     * 双红相邻
     * 叔叔节点 黑色 自己是右  左旋
     */
    private void checkBalance(Node node) {
        if (node.getFather().getColor() == Node.BLACK) {
            return;
        }
        Node gradeFather = node.getFather().getFather();
        boolean isLeft = gradeFather.getLeft() == node.getFather();
        // 父节点 红色以及叔叔节点也是红色的
        if (gradeFather.getLeft().getColor() == Node.RED && gradeFather.getRight().getColor() == Node.RED) {
            // 1 让 祖父节点变为红色 父叔节点
            gradeFather.setColor(Node.RED);
            gradeFather.getLeft().setColor(Node.BLACK);
            gradeFather.getRight().setColor(Node.BLACK);
            checkBalance(node.getFather());
        }
        if (isLeft) {
        // 父亲节点 红色 且 父亲节点是祖父节点的左孩子
            rightRotate(node.getFather()); //右旋
            node.getFather().setColor(Node.BLACK);
            if (node.getFather().getRight() != null) {
                node.getFather().getRight().setColor(Node.BLACK);
            }
        }else{
        // 父亲节点 红色 且 父亲节点是祖父节点的右孩子
            leftRotate(node);
        }

    }


    private Node findTarget(Node root, Node node) {
        Node temp = root;
        while (temp != null) {
            if (temp.getValue() <= node.getValue()) {
                if (temp.getRight() == null) return temp;
                temp = temp.getRight();
            } else {
                if(temp.getLeft() ==null) return temp;
                temp = temp.getLeft();
            }
        }
        return temp;
    }


    /**
     * 左旋
     * @param node
     */
    private void leftRotate(Node node) {
        Node father = node.getFather();
        Node gradeFather = node.getFather().getFather();

        father.setRight(node);
        node.getLeft().setFather(father);

        gradeFather.setLeft(node);
        node.setFather(gradeFather);

        father.setFather(node);
        node.setLeft(father);


    }


    /**
     * 右旋
     * @param node
     */
    private void rightRotate(Node node) {
        Node father = node.getFather();
        Node gradeFather = node.getFather().getFather();

        father.setLeft(node.getRight());
        node.getRight().setFather(father);

        node.setRight(father);
        father.setFather(node);

        node.setFather(gradeFather);
        gradeFather.setLeft(node);

    }



    public static void main(String[] args) {

        RBtree rBtree = new RBtree();
        rBtree.add(new Node(Node.BLACK, null, null, 5));
        rBtree.add(new Node(Node.BLACK, null, null, 2));
        rBtree.add(new Node(Node.BLACK, null, null, 10));
        rBtree.add(new Node(Node.BLACK, null, null, 7));
        rBtree.add(new Node(Node.BLACK, null, null, 11));
        rBtree.add(new Node(Node.BLACK, null, null, 1));
        rBtree.add(new Node(Node.BLACK, null, null, 3));

        TreePrinter.print(rBtree.getRoot());

    }


}
